#include <fstream>
#include <iostream>

using namespace std;

const int N = 9;
const int M = 2;

// line记录每一行(X)国王的个数
int line[N + 2] = {0};
// col记录每一列(X)国王的个数
int col[N + 2] = {0};
// board记录棋盘board[x][y]==0表示空位置， board[x][y]==1表示该位置放有国王
int board[N + 2][N + 2] = {0};
int total_cnt;

bool isPlaceOK(int n, int c)
{
	//检查同一行是否已有M个国王
	if (line[n] >= M)
		return false;
	//检查同一列是否已有M个国王
	if (col[c] >= M)
		return false;

	//检查n-1行的c-1, c, c+1位置是否有国王
	if (board[n - 1][c] | board[n - 1][c - 1] | board[n - 1][c + 1])
		return false;
	//检查n行的c-1, c+1位置是否有国王
	if (board[n][c - 1] | board[n][c + 1])
		return false;
	//检查n+1行的c-1, c, c+1位置是否有国王
	if (board[n + 1][c] | board[n + 1][c - 1] | board[n + 1][c + 1])
		return false;

	return true;
}

void printSol()
{
	cout << "Solution: " << total_cnt << endl;
	for (int i = 1; i <= N; ++i)
	{ //遍历每一行
		for (int j = 1; j <= N; ++j)
		{	//遍历每一列
			//如果标记数组中这一行的国王放在j位置，则输出X，否则输出-，
			cout << (board[i][j] == 1 ? "X" : "-") << " ";
			;
		}
		//用空格分隔
		cout << endl; //每一行输出一个换行
	}
	cout << endl; //每一组数据一个换行分隔
	// getchar();
}

void addKings(int n, int c)
{
	if (c > N)
		return;
	if (n > N)
	{ // n代表从第一行开始放置
		printSol();
		total_cnt++;
		return;
	}
	for (int i = c; i <= N; ++i)
	{ // i从第1列到第N列遍历
		if (isPlaceOK(n, i))
		{
			//如果可以放置，就把国王放在第n行第i列
			col[i]++; 
			line[n]++;
			board[n][i] = 1;
			if (line[n] == M)
			{
				addKings(n + 1, 1);
			}
			else
			{
				addKings(n, i + 1);
			}
			//当回溯(查找新方案)时，需要清除原来的痕迹
			board[n][i] = 0;
			col[i]--;
			line[n]--;
		}
	}
}

int main()
{
	static std::ofstream g_log("result.txt");
	std::cout.rdbuf(g_log.rdbuf());

	addKings(1, 1);
	cout << "total: " << total_cnt << " solutions.\n";
	return 0;
}
